/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-08-28
 * Time: 15:26
 */

/**
 *将 x 减到 0 的最小操作数:
 *
 * 给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
 *
 * 如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,1,4,2,3], x = 5
 * 输出：2
 * 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
 * 示例 2：
 *
 * 输入：nums = [5,6,7,8,9], x = 4
 * 输出：-1
 * 示例 3：
 *
 * 输入：nums = [3,2,20,1,1,3], x = 10
 * 输出：5
 * 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
 */
public class OperandMin {
    //解法：运用滑动窗口

    /**sum是数组总和
     n为数组总长度
     把问题转化为：找出最长子数组的长度len，子数组的所有元素的总和等于sum-x(tagert)
     tagert = sum-x

     更新结果n-len
     */
    public int minOperations(int[] nums, int x) {

        int sum = 0;
        int n = nums.length;
        int tagert = sum-x;
        for(int a : nums){
            sum += a;
            tagert = sum - x;
        }

        //细节，[1,1]数组数量很少sum - x 小于 0
        if(tagert < 0) return -1;

        int len = -1;//没有最终结果返回-1
        for(int left = 0, right = 0,total = 0; right < n; right++){
            //进窗口
            total += nums[right];

            //凑出tagert == total
            while(total > tagert){
                total -= nums[left++];//出窗口
            }

            //更新结果len
            if(total == tagert){
                len = Math.max(len,right-left+1);
            }
        }
        if(len == -1) return len;
        else return n-len;
    }
}
